package demo.DataStrucAndAlgo.Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.List;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/30-07-30-16:30
 * @Description：demo.DataStrucAndAlgo.Graph    图的广度优先遍历
 */
/*
图的广度优先遍历BFS
    先从指定索引位置出门，输出该顶点的信息，并设置为已访问，将其加入到队列中
    进入循环，从队列头取出之前保存的顶点，通过邻接矩阵判断其是否有直接相连且
    没被访问的下一个顶点，有了就输出该顶点信息，并设置为访问，将其加入到队列中
    ，没有就进行下一次循环。直到队列中没有顶点为止
 */
public class Graph_BFS {
    private ArrayList<Character> vertexList;
    private int[][] edges;
    private int numOfEdge;
    private boolean[] isVisited;
    public Graph_BFS(int num){
        vertexList = new ArrayList<>();
        edges = new int[num][num];
        numOfEdge = 0;
        isVisited = new boolean[num];
    }
    public void BFS(int n){
        LinkedList<Character> list = new LinkedList<>();
        System.out.print((char)getVertexByIndex(n));
        isVisited[n] = true;
        list.add((char)getVertexByIndex(n));
        while(!list.isEmpty()){
            int index = list.remove()-'A';
            for (int i = 0; i < edges[index].length; i++) {
                if(edges[index][i] != 0 && !isVisited[i]){
                    isVisited[i] = true;
                    System.out.print(" -> " + (char)getVertexByIndex(i));
                    list.add((char)getVertexByIndex(i));
                }
            }
        }

    }
    public void insertVertex(char vertex){
        vertexList.add(vertex);
    }

    /**
     * 无向图
     * @param v1       顶点1
     * @param v2     顶点2
     * @param weight    权值
     */
    public void insertEdges(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdge++;
    }
    public int getNumOfVertex(){
        return vertexList.size();
    }
    public int getNumOfEdge(){
        return numOfEdge;
    }
    public int getVertexByIndex(int index){
        return vertexList.get(index);
    }
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    public void show(){
        for (int i = 0; i < edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }

    public static void main(String[] args) {
        Graph_BFS graph = new Graph_BFS(5);
        for (int i = 0; i < 5; i++) {
            graph.insertVertex((char)('A' + i));
        }
        //添加边：A-B,A-C,C-B,B-E,B-D
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(2,1,1);
        graph.insertEdges(1,4,1);
        graph.insertEdges(1,3,1);
        System.out.println("邻结矩阵为：");
        graph.show();
        System.out.println("A-B边权值为：");
        System.out.println(graph.getWeight(0,1));
        System.out.println("D顶点的数据为：" + (char)graph.getVertexByIndex(3));
        System.out.println("含有的边数位：" + graph.getNumOfEdge());
        System.out.println("-------------------");
        graph.BFS(3);
    }
}
